package elementaryAlgorithm;

/**
 * @author 郭辉
 * @className TODO
 * @description 37. 解数独
 * 编写一个程序，通过填充空格来解决数独问题。
 *
 * 数独的解法需 遵循如下规则：
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [['5','3','.','.','7','.','.','.','.'],['6','.','.','1','9','5','.','.','.'],['.','9','8','.','.','.','.','6','.'],['8','.','.','.','6','.','.','.','3'],['4','.','.','8','.','3','.','.','1'],['7','.','.','.','2','.','.','.','6'],['.','6','.','.','.','.','2','8','.'],['.','.','.','4','1','9','.','.','5'],['.','.','.','.','8','.','.','7','9']]
 * 输出：[['5','3','4','6','7','8','9','1','2'],['6','7','2','1','9','5','3','4','8'],['1','9','8','3','4','2','5','6','7'],['8','5','9','7','6','1','4','2','3'],['4','2','6','8','5','3','7','9','1'],['7','1','3','9','2','4','8','5','6'],['9','6','1','5','3','7','2','8','4'],['2','8','7','4','1','9','6','3','5'],['3','4','5','2','8','6','1','7','9']]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 *
 *
 *
 *
 * 提示：
 *
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字或者 '.'
 * 题目数据 保证 输入数独仅有一个解
 * 通过次数196,945提交次数291,341
 * @date 2023/4/1 9:25
 * @company 海康威视
 * @since 1.0.0
 */
public class Leet37 {
    char[][] board;
    char[] chars = {'0','1','2','3','4','5','6','7','8','9'};
    public void solveSudoku(char[][] board) {

        this.board = board;
        suDu(this.board,0,0);
    }

    //返回条件
    //路径
    //选择：1~9
    public void suDu(char[][] board,int row,int col){
        //返回条件
        if (row >= 9 || col >=9){
            return;
        }
        while (row < 9){
            for (int i = col; i < 9; i++) {
                if (board[row][i] != '.'){
                    continue;
                }
                for (int k = 1; k < 10 ; k++) {
                    //剪枝
                    if (!vaild(board,row,i,k)){
                        continue;
                    }
                    //选择
                    board[row][i] = chars[k];
                    suDu(board,row,i+1);
                    //撤销
                    board[row][i] = '.';
                }
                if (board[row][i] == '.'){
                    return;
                }
            }
            row++;
        }
    }

    private boolean vaild(char[][] board, int row, int col, int k) {
        //行唯一
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == chars[k]) return false;
        }
        //列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == chars[k]) return false;
        }
        //3x3
        int rStart,lStart;
        if (row<=3){
            rStart = 0;
        }else if (row>3 && row <=5){
            rStart = 3;
        }else {
            rStart = 6;
        }
        if (col<=3){
            lStart = 0;
        }else if (col>3 && col <=5){
            lStart = 3;
        }else {
            lStart = 6;
        }
        for (int i = rStart; i < rStart+3 ; i++) {
            for (int j = lStart; j < lStart+3; j++) {
                if (board[i][j] == chars[k]){
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] param =  {
                {'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},
                {'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},
                {'4','.','.','8','.','3','.','.','1'},
                {'7','.','.','.','2','.','.','.','6'},
                {'.','6','.','.','.','.','2','8','.'},
                {'.','.','.','4','1','9','.','.','5'},
                {'.','.','.','.','8','.','.','7','9'}
    };
       Leet37 leet37 = new Leet37();
       leet37.solveSudoku(param);
        System.out.println(leet37.board.toString());
    }
}
